package Array_and_String;

/*
长度最小的子数组
给定一个含有n个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组[4,3]是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/c0w4r/
 */

import java.util.Arrays;

public class _46长度最小的子数组 {
    public static void main(String[] args) {

        int[] n = {1, 4, 4};

        System.out.println(minSubArrayLen3(9, n));

    }

    //暴力枚举:  会超出时间限制
    public static int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum < target) {
            return 0;
        }
        int minlen = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            int len = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                len++;
                if (sum >= target) {
                    minlen = Math.min(minlen, len);
                    break;
                }
            }
        }
        return minlen;
    }

    //方法二:  下标 ＋ 二分查找
    public static int minSubArrayLen2(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    //方法三：  滑动窗口
    public static int minSubArrayLen3(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int len = Integer.MAX_VALUE;
        int slow = 0,fast = 0;
        int sum = 0;
        while (fast < n){
            sum += nums[fast];
            while (sum >= target) {
                len = Math.min(len, fast - slow + 1);
                sum -= nums[slow];
                slow++;
            }
            fast++;
        }

        return len == Integer.MAX_VALUE ? 0 : len;
    }

}
